package newcoder_exp.justPractise;

import java.util.Arrays;

import org.junit.Test;

public class NC135 {

    public class Solution {
        //有冷冻期。。。。
        public int maxProfit1(int[] prices) {
            if (prices == null || prices.length <= 1)
                return 0;
            int len = prices.length;
            int[][] f = new int[len][3];
            // f[i][0]表示不持有，且不是今天卖出去的
            // f[i][1]表示持有
            // f[i][2]表示不持有，且就是今天卖出去的
            f[0][0] = 0;
            f[0][1] = -prices[0];
            f[0][2] = 0; // 买了又卖了

            for (int i = 1; i < len; i++) {
                f[i][0] = Math.max(f[i - 1][2], f[i - 1][0]);
                f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - prices[i]);
                f[i][2] = Math.max(f[i - 1][1] + prices[i], f[i - 1][0]);
            }
            System.out.println(Arrays.deepToString(f));
            return Math.max(f[len - 1][0], f[len - 1][2]);
        }

        //不限制购买次数
        public int maxProfit2(int[] prices) {
            if (prices == null || prices.length <= 1)
                return 0;
            int len = prices.length;
            int[][] f = new int[len][2];
            f[0][0] = 0;
            f[0][1] = -prices[0];
            for (int i = 1; i < len; i++) {
                f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]);
                f[i][1] = Math.max(f[i - 1][0] - prices[i], f[i - 1][1]);
            }
            return f[len - 1][0];
        }

        public int maxProfit(int[] prices) {
            if (prices == null || prices.length <= 1)
                return 0;
            int len = prices.length;
            int[][][] f = new int[len][2][3];
            f[0][0][2] = 0;
            f[0][1][1] = -prices[0];
            f[0][1][0] = -prices[0];
            f[0][0][0] = 0;
            f[0][0][1] = 0;
            for (int i = 1; i < len; i++) {
               f[i][1][0] = Math.max(f[i - 1][1][0], f[i - 1][0][1] - prices[i]);
               f[i][1][1] = Math.max(f[i - 1][1][1], f[i - 1][0][2] - prices[i]);
               f[i][0][0] = Math.max(f[i - 1][0][0], f[i - 1][1][0] + prices[i]);
               f[i][0][1] = Math.max(f[i - 1][0][1], f[i - 1][1][1] + prices[i]);
               f[i][0][2] = f[i - 1][0][2];
            }
            return Math.max(f[len - 1][0][1], f[len - 1][0][0]);
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{8,9,3,5,1,3};
        int res = s.maxProfit(nums);
        System.out.println(res);
    }
}
